package 普通数组.最大子数和;

/**
 * 题目思路
 * 用历史信息推导出当前信息的最优解
 * 一个状态记录以当前位置为结尾的子树组的最大和
 * nums[i] 结尾的前面的最大子数和
 * dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
 * */

class Solution1 {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n]; // 定义dp数组
        dp[0] = nums[0]; // 初始化第一个状态
        int maxSum = dp[0];

        // 从第二个元素开始遍历
        for(int i = 1; i < n;i++){
            // 状态转移方程
            dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
            // 更新全局最大值
            maxSum = Math.max(maxSum,dp[i]);
        }
        return maxSum; // 返回最大子数的和
    }
    public static void main(String[] args){
        Solution solution = new Solution();
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(solution.maxSubArray(nums));
    }
}